#include "thread.h"

extern func_BiTree fBiTree;

/**
 *  功 能：
 *      线索化二叉树 -- 后序线索化
 *  参 数：
 *      root：要线索化的树的根节点
 *      ptmp：用于保留前驱节点
 *  返回值：
 *      无
 **/
void post_thread(BiTNode *root, BiTNode **ptmp)
{
    if ((root == NULL))
        goto END;

    post_thread(root->lchild, ptmp);
    post_thread(root->rchild, ptmp);

    if (root->lchild == NULL)
    {
        root->lchild = *ptmp;
        root->lTag = 1;
    }
    if (*ptmp != NULL && (*ptmp)->rchild == NULL)
    {
        (*ptmp)->rchild = root;
        (*ptmp)->rTag = 1;
    }
    (*ptmp) = root;

END:
    return;
}

/**
 *  功 能：
 *      后序线索化二叉树的前驱节点 
 *  参 数：
 *      root：要查找的节点
 *  返回值：
 *      成功：节点的后继节点
 *      失败：NULL
 **/
BiTNode *post_thread_prevNode(BiTNode *root)
{
    BiTNode *ret = NULL;

    if (root == NULL)
        goto END;

    // 如果 lTag 为 1, 就是本应该的前驱节点
    if (root->lTag == 1)
        ret = root->lchild;
    // 如果右孩子存在并且 rTag 不为 1, 那么 rchild 指针域就是前驱节点
    else if (root->rchild && root->rTag != 1)
        ret = root->rchild;
    // 如果 rTag 为 0, 并且同时 rTag 为0， 那么 rchild 指针域就是前驱节点
    // 这是因为在左右子树都存在的情况下，不会去进行线索化，但是其节点总归要前驱
    // 节点和后继节点的其中一个
    else if (root->lTag == 0 && root->rTag == 1)
        ret = root->lchild;
    else
        ret = root->lchild;

END:
    return ret;
}

/**
 *  功 能：
 *      后序线索化二叉树的后继节点 
 *  参 数：
 *      root：要查找的节点
 *  返回值：
 *      成功：节点的后继节点
 *      失败：NULL
 **/
BiTNode *post_thread_nextNode(BiTNode *root)
{
    BiTNode *ret = NULL;
    if (root == NULL)
        goto END;

    if (root->rTag == 1) // 官方指定的后继节点
    {
        ret = root->rchild;
    }
    else
    {
        BiTNode *parent = root->parent; //prev_thread_parent(root);

        if (parent == NULL) // 根节点，无后继节点
            ret = NULL;
        else if (root == parent->rchild) // 双亲的右孩子，则其后继为其双亲；
        {
            ret = parent;
        }
        else if (root == parent->lchild && parent->rTag == 1) // 双亲无右子女，则其后继为其双亲；
        {
            ret = parent;
        }
        else if (root == parent->lchild && parent->rTag == 0) //  双亲有右子女
        {
            root = parent->rchild;                  // 其双亲的右子树中 按后序遍历的第一个结点。
            while (root != NULL && root->lTag == 0) // 要求是左子树
            {
                root = root->lchild;
            }

            if (root != NULL && root->rTag == 0) // 说明最左节点还有右孩子
            {
                root = root->rchild;
                if (root->lTag == 0) // 说明存在左孩子，需要移动到当前左孩子身边
                {
                    while (root != NULL && root->lTag == 0)
                        root = root->lchild;
                }
            }

            ret = root;
        }
    }

END:
    return ret;
}

/**
 *  功 能：
 *      遍历线索化二叉树 - 使用后继节点
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void post_thread_Older_byNextNode(BiTNode *root)
{
    if (root == NULL)
        goto END;

    // 找到后序遍历的第一个节点
    while (root != NULL && root->lTag == 0) // 要求是左子树
    {
        root = root->lchild;
    }

    if (root != NULL && root->rTag == 0) // 说明最左节点还有右孩子
    {
        root = root->rchild;
        if (root->lTag == 0) // 说明存在左孩子，需要移动到当前左孩子身边
        {
            while (root != NULL && root->lTag == 0)
                root = root->lchild;
        }
    }

    while (root)
    {
        printf("%c ", root->data);
        root = post_thread_nextNode(root);
    }
END:
    printf("\n");
    return;
}

/**
 *  功 能：
 *      遍历线索化二叉树 - 使用前驱节点
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void post_thread_Older_byPrevNode(BiTNode *root)
{
    if (root == NULL)
        goto END;

    while (root)
    {
        printf("%c ", root->data);
        root = post_thread_prevNode(root);
    }

END:
    printf("\n");
    return;
}

/**
 *  功 能：
 *      遍历线索化二叉树 -- 常规遍历
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void post_thread_Older_normal(BiTNode *root)
{
    BiTNode *prev = NULL;

    if (root == NULL)
        goto END;

    while (root != NULL)
    {
        // 定位到树最左边的节点
        while (root->lchild != prev && root->lTag == 0)
            root = root->lchild;

        // root->rTag 访问当前节点的后继节点
        while (root != NULL && root->rTag == 1)
        {
            printf("%c ", root->data);
            prev = root;
            root = root->rchild;
        }

        // 如果上一次访问记录的节点与当前节点的右孩子重复，则说明当前节点的左子树已经访问完成
        while (root != NULL && root->rchild == prev)
        {
            printf("%c ", root->data);
            prev = root;
            root = root->parent;
            /*
				其实可以用栈实现保存每层的父节点
				递归一层就把节点压栈
				回溯一层就出栈并获取栈顶
				所以就在Node的定义里加了个父节点的指针
				不然我个人建议是用栈的
			*/
        }

        // 开始遍历右子树
        if (root != NULL && root->rTag == 0)
        {
            root = root->rchild;
            if (root->lTag == 0) // 说明存在左孩子，需要移动到当前左孩子身边
            {
                while (root != NULL && root->lTag == 0)
                    root = root->lchild;
            }
        }
    }

END:
    printf("\n");
    return;
}
/**
 *  功 能：
 *      先序线索化二叉树的双亲节点
 *  参 数：
 *      root ：树的根节点
 *      child：要获取双亲节点的节点
 *  返回值：
 *      成功：child节点双亲节点
 *          注意：当child为根节点的时候，返回也是NULL
 *      失败：NULL
 **/
BiTNode *prev_thread_parent(BiTNode *root, BiTNode *child) //找孩子的双亲
{
    BiTNode *ret = NULL;

    if (root == NULL || child == NULL || root == child)
        goto END;

    //这里已经将叶子节点指针域线索化成了前驱和后继，所以得加另外的限制
    if ((root->lTag != 1 && root->lchild == child) || (root->rTag != 1 && root->rchild == child))
    {
        ret = root;
        goto END;
    }

    if (root->lTag != 1) //这里同样是要判断是左右孩子还是前驱后继，否则就会造成循环
        ret = prev_thread_parent(root->lchild, child);
    if (ret == NULL && root->rTag != 1)
        ret = prev_thread_parent(root->rchild, child);
END:
    return ret;
}

funThread fthread = {
    post_thread,

    post_thread_Older_byNextNode,
    post_thread_Older_byPrevNode,
    post_thread_Older_normal,

    post_thread_nextNode,
    post_thread_prevNode,
    prev_thread_parent};

#if 0

#endif
